#include <iostream>
#include <list>
#include <ctime>
#include <fstream>
#include <sstream>
#include <queue>
#include <stack>

using namespace std;


void random(int n, int &m, list<int>* voisins);
bool estVoisin(list<int> *voisins, int x, int y);
void pLargeur(int n, int r, list<int>* voisins, int* pere, int* ordre, int* niveau);
void pProfondeur(int n, int r, list<int>* voisins, int* pere, int* debut, int* fin);


void DrawGraph(int n, list<int>* voisins);


int main()
{
	srand (time(NULL));
	
	int n;	// SOMMET
	int m;	// ARETE
	
	cout << "Entrez le nombre de Sommet : ";
	cin >> n;
	cout << "Entrez le nombre d'Arete : ";
	cin >> m;
	
	list<int> *voisins = new list<int>[n];
	int *pere = new int[n];
	int *ordre = new int[n];
	int *niveau = new int[n];
	int *debut = new int[n];
	int *fin = new int[n];
	
	random(n, m, voisins);
	DrawGraph(n, voisins);
	
	pLargeur(n, 0, voisins, pere, ordre, niveau);
	pProfondeur(n, 0, voisins, pere, debut, fin);
	
	for(int i(0); i<n; i++)
	{
		cout << "i:" << i << "p:" << pere[i] << "o:" << ordre[i] << "n:" << niveau[i] << "d:" << debut[i] << "f:" << fin[i] << endl;
	}
	
// 	delete voisins;
// 	delete pere;
// 	delete ordre;
// 	delete niveau;
	
	return 0;
}

bool estVoisin(list<int>* voisins, int x, int y)
{
	for(list<int>::iterator it = voisins[x].begin(); it != voisins[x].end(); ++it)
	{
		if((*it) == y)
		{
			return true;
		}
	}
	
	return false;
}

void random(int n, int &m, list<int>* voisins)
{
	int k = 0;
	
	while(k<=m || k >= n*(n-1)/2)
	{
		int x = rand() % n;
		int y = rand() % n;
		
		while(x != y && estVoisin(voisins, x, y))
		{
			x = rand() % n;
			y = rand() % n;
		}
		
		k++;
		
		voisins[x].push_back(y);
		voisins[y].push_back(x);
	}
	
	m=k;
}

void pLargeur(int n, int r, list<int>* voisins, int* pere, int* ordre, int* niveau)
{
	int* dv = new int[n];
	for(int i(0);i<n;i++)
	{
		dv[i] = 0;
	}
	
	dv[r] = 1;
	ordre[r] = 1;
	pere[r] = r;
	niveau[r] = 0;
	
	queue<int> file;
	
	file.push(r);
	
	int t = 2;
	
	while(!file.empty())
	{
		int k = file.front();
		file.pop();
		
		for(list<int>::iterator it = voisins[k].begin(); it != voisins[k].end(); ++it)
		{
			if(dv[*it] == 0)
			{
				dv[*it] = 1;
				
				file.push(*it);
				
				ordre[*it] = t;
				t++;
				pere[*it] = k;
				niveau[*it] = niveau[k] + 1;
			}
		}
	}
}


void pProfondeur(int n, int r, list<int>* voisins, int* pere, int* debut, int* fin)
{
	int* dv = new int[n];
	for(int i(0);i<n;i++)
	{
		dv[i] = 0;
	}
	
	dv[r] = 1;
	debut[r] = 1;
	pere[r] = r;
	
	stack<int> pile;
	
	pile.push(r);
	
	int t = 2;
	
	while(!pile.empty())
	{
		int k = pile.top();
		
		if(voisins[k].empty())
		{
			pile.pop();
			fin[k] = t;
			t++;
		}
		else
		{
			int y = voisins[k].front();
			voisins[k].pop_front();
			
			if(dv[y] == 0)
			{
				dv[y] = 1;
				pile.push(y);
				debut[y] = t;
				t++;
				pere[y] = k;
			}
		}
	}
}













void DrawGraph(int n, list<int>* voisins)
{
	std::string sortie;

	int k(0);
	
	for(int i(0); i<n; i++)
	{
		std::ostringstream oNum, oLign, oCol;
	
		oNum << i;
		oLign << (i % 8) * 2;
		oCol << (i + k%7 + rand() % 2) % 23;
		sortie += "\\node[draw] (SZ"+oNum.str()+") at ("+oLign.str()+", "+oCol.str()+") { "+oNum.str()+"};\n";

		k += 3;
	}
	
	for(int i(0); i<n; i++)
	{
		std::ostringstream oLign;
		
		oLign << i;
		
		for(list<int>::iterator it = voisins[i].begin(); it != voisins[i].end(); it++)
		{
			std::ostringstream oCol;
			//cout << (*it) << "+" << i << ":";
			oCol << (*it);
			sortie += "\\draw (SZ"+oLign.str()+") -- (SZ"+oCol.str()+");\n";
		}
	}
	
	sortie = "\\documentclass[a4paper]{article} \n \\usepackage{tikz} \n \\begin{document} \n \\begin{tikzpicture}\n" + sortie + "\n  \\end{tikzpicture}\n  \\end{document} \n";
	
	ofstream file("graph.tex");
	file << sortie;
	
	cout << "end" << endl;
}
